class Solution
{
public:
    bool possibleBipartition(int n, vector<vector<int>> &dislikes)
    {
        vector<int> group(n + 1, 0);
        vector<vector<int>> adjTable(n + 1, vector<int>());
        for (auto &dislike : dislikes)
        {
            adjTable[dislike[0]].push_back(dislike[1]);
            adjTable[dislike[1]].push_back(dislike[0]);
        }
        for (int i = 1; i <= n; ++i)
        {
            if (group[i] == 0)
            {
                group[i] = 1;
                queue<int> q;
                q.push(i);
                while (!q.empty())
                {
                    int cur = q.front();
                    q.pop();
                    for (int next : adjTable[cur])
                    {
                        if (group[next] != 0 && group[next] == group[cur])
                        {
                            return false;
                        }
                        if (group[next] == 0)
                        {
                            group[next] = 3 - group[cur];
                            q.push(next);
                        }
                    }
                }
            }
        }
        return true;
    }
};